/*
	contains the code to initialise the memory sub-system

	Author: Aidan Goddard 27/6/14
*/

#include "types.h"
#include "memory.h"
#include "memory_offsets.h"
#include "memory_tables.h"
#include "printf.h"
#include "kmemory.h"
#include "kernel_fixed_table.h"

//#define DEBUG_TEST_HIGH_ADDRESS
#define DEBUG_TEST_ADDRESS (256ULL * 1024 * 1024 * 1024 * 1024 - 1)

//////////////////////////////////////////////////////////////////////////////////////////////////////
// routines


extern struct physical_allocation_control *phys_allocation_control;
extern uint8_t *bitmap_4kb;
extern uint64_t bitmap_4kb_length;
extern uint8_t *bitmap_8kb;
extern uint64_t bitmap_8kb_length;
extern uint8_t *bitmap_16kb;
extern uint64_t bitmap_16kb_length;
extern uint8_t *bitmap_32kb;
extern uint64_t bitmap_32kb_length;

extern struct virtual_allocation_control *vir_allocation_control;
extern uint8_t *vir_bitmap_2mb;
extern uint64_t vir_bitmap_2mb_length;

extern struct bios_memory_entry *entries;
extern uint16_t entry_count;


static void build_virtual_bitmap(uint64_t physical_bitmap_4kb_pages)
{
	// map kernel PD0 into the PD mapping area
	uint64_t *kernel_PD_area_PT = (uint64_t*)(KOFFSET + PHYSICAL_PD_AREA_PT);
	kernel_PD_area_PT[0] = PHYSICAL_PD_KERNEL0 | 0x103;

	// map the PD area PT into the kernel 0 PD at 18MB
	uint64_t *kernel_PD_0 = (uint64_t*)(KOFFSET + PHYSICAL_PD_KERNEL0);
	kernel_PD_0[9] = PHYSICAL_PD_AREA_PT | 0x3;

	// map in virtual allocation map PT at 16MB
	kernel_PD_0[8] = PHYSICAL_VIRTUAL_MAP_PT_BASE | 0x3;

	// get pointer to base of virutal allocation bitmap
	vir_bitmap_2mb = (uint8_t*)VIRTUAL_ALLOCATION_BITMAP_2MB;

	// determine number of PDs that are mapped into the kernel
	uint64_t PDs_mapped = physical_bitmap_4kb_pages / 0x40000;
	if(physical_bitmap_4kb_pages % 0x40000 > 0)
		PDs_mapped++;

	printf("PDs mapped %u", PDs_mapped);

	// determine length of the bitmap
	vir_bitmap_2mb_length = (512 * 512) / 8;	// (PTs per PD * max PDs) / bits per byte

	// determine number of 4kb pages required for the bitmap
	uint64_t pages_for_2mb_bitmap = vir_bitmap_2mb_length / 0x1000; // should be 8 exactly
	
	printf("pages required for 2mb virtual space bitmap %u", pages_for_2mb_bitmap);
	
	// get pointer to base of virtual allocaiton map PTs
	uint64_t *virtual_allocation_map_PT = (uint64_t*)(KOFFSET + PHYSICAL_VIRTUAL_MAP_PT_BASE);

	// setup the 2mb virtual address space map
	printf("building kernel virtual space allocation 2mb bitmap");
	int i;
	for(i = 0; i < pages_for_2mb_bitmap; i++)
	{
		// try to get a memory page from the high memory area
		uint64_t new_4kb_page = memory_get_page(PAGE_SIZE_4K, PAGE_TYPE_HIGH);
		if(!new_4kb_page)
		{
			// could not allocate from high memory area, get form low memory area
			new_4kb_page = memory_get_page(PAGE_SIZE_4K, PAGE_TYPE_LOW);
		}

		// increase kernel memory allocated
		phys_allocation_control->kernel_memory_allocated += 4096;

		// now have the page, map it in
		virtual_allocation_map_PT[i] = new_4kb_page | 0x103;
	}

	// invalidate addresses up to KOFFSET + 20MB
	for(i = 0; i < 10; i++)
		invlpg(KOFFSET + 0x1000000 + (i * 4096));
	
	// set first 10 entries in the PT bitmap to used (first 20MB of kernel space)
	vir_bitmap_2mb[0] = 0xff;
	vir_bitmap_2mb[1] = 0x3;

	// set all entries above the first GB as non-available
	for(i = 1; i < 512; i++)
	{
		// for each byte in the bitmap
		int k;
		for(k = 0; k < 64; k++)
		{
			vir_bitmap_2mb[(i * 64) + k] = 0xff;
		}
	}

	// setup allocation control area
	vir_allocation_control = (struct virtual_allocation_control*)(KOFFSET + PHYSICAL_VIRTUAL_ALLOC_CONTROL);
	vir_allocation_control->available_virtual_memory = 502 * 2097152;
	vir_allocation_control->available_2mb_PTs = 502;
	vir_allocation_control->next_available_2mb_PT = 0;
	vir_allocation_control->physical_bitmap_PD_count = PDs_mapped;

	printf("kernel memory allocated so far %uB %uKB", phys_allocation_control->kernel_memory_allocated, phys_allocation_control->kernel_memory_allocated / 1024);

	// finished
	return;
}

static uint64_t *build_bitmap_virtual_space(uint64_t bitmap_address, uint64_t pages_required_4kb)
{
	// this function is responsible for creating the address space for the physical allocation bitmap to reside in
	// do the physical page bitmap mapping
	// check how many pages can be mapped directly as 2mb
	// and how many will be left over to map as 4kb
	uint64_t pages_2mb = pages_required_4kb / 512;	// 512 4kb pages per 2mb page
	uint64_t pages_4kb = pages_required_4kb % 512;

	// report them
	printf("4kb pages required for physical allocation bitmap: %u", pages_4kb);
	printf("2mb pages required for physical allocation bitmap: %u", pages_2mb);

	// determine how many GB are required for the physical bitmap
	// number of GB = number of Page Directory tables that need to be mapped in
	uint64_t PD_count = pages_required_4kb / 262144; // (256k)
	if(pages_required_4kb % 262144 > 0)
		PD_count += 1;

	// report PD count
	//printf("mapping %u PD tables for bitmap into kernel VM space", PD_count);

	// get virtual address of kernel PDP
	// and kernel PD area PT
	uint64_t *kernel_PDP = (uint64_t*)(KOFFSET + PHYSICAL_PDP_KERNEL);
	uint64_t *kernel_PD_area_PT = (uint64_t*)(KOFFSET + PHYSICAL_PD_AREA_PT);

	// get pointer to the PDs
	uint64_t *bitmap_PDs = (uint64_t*)(KOFFSET + PHYSICAL_PAGE_MAP_PD_16_BASE);

	// and get base address of the physical bitmap PDs & the corresponding base virtual address
	uint64_t bitmap_PD_physical_address = PHYSICAL_PAGE_MAP_PD_16_BASE;
	uint64_t bitmap_PD_virtual_address = KOFFSET + 0x40000000ULL;

	// map each of the PD tables in
	printf("mapping %u PD tables", PD_count);
	uint64_t i;
	for(i = 0; i < PD_count; i++)
	{
		// report
		printf("mapping PD %u at 0x%x to 0x%a", i, bitmap_PD_physical_address, bitmap_PD_virtual_address);

		// map it to the kernel PDP
		kernel_PDP[i + 1] = bitmap_PD_physical_address | 0x3;

		// also map it into the PD map table
		kernel_PD_area_PT[i + 1] = bitmap_PD_physical_address | 0x103;

		// now need to map PD entries to 2MB pages or the 4KB pages PT
		// calculate how many 2MB pages remain to be mapped
		uint64_t remaining_2mb_pages = pages_2mb - (i * 512);
		uint64_t map_base_2mb = bitmap_address + (i * 512 * 2097152ULL); // i * 512 * 2M

		// get index into bitmap PD entries for this GB
		uint64_t index = (i * 512);

		// map them
		uint64_t k;
		for(k = 0; k < 512 && k < remaining_2mb_pages; k++)
		{
			//printf("mapping 2mb page %u at 0x%a to 0x%a", k + index - 512, (map_base_2mb + (0x200000 * k)), V_address + (k * 0x200000));
			bitmap_PDs[index + k] = (map_base_2mb + (0x200000 * k)) | 0x183;
			invlpg(bitmap_PD_virtual_address + (k * 0x200000));
		}

		// check if ran out of 2mb pages early
		if(k < 512)
		{
			// map the 4kb PT to the PDE pointed to by index + k
			bitmap_PDs[index + k] = PHYSICAL_PAGE_MAP_LEFTOVER_PT | 0x3;

			// fill in the PT
			// get base address of PT
			uint64_t *PT = (uint64_t*)(KOFFSET + PHYSICAL_PAGE_MAP_LEFTOVER_PT);

			// get physical base address of 4k pages to use
			uint64_t map_base_4kb = map_base_2mb + (0x200000 * k);

			// fill in the entries
			int j;
			for(j = 0; j < pages_4kb; j++)
			{
				PT[j] = (map_base_4kb + (j * 4096)) | 0x103;
				invlpg(bitmap_PD_virtual_address + (k * 0x200000) + (j * 4096));
			}

		}

		// update physical and virtual address for next entry
		bitmap_PD_physical_address += 4096;				// add 4k
		bitmap_PD_virtual_address += 0x40000000ULL;		// add 1GB
	}

	//printf("physical memory bitmap located at virtual 0x%a", KOFFSET + 0x40000000);

	return (uint64_t*)(KOFFSET + 0x40000000);
}

static uint64_t build_bitmap(uint64_t *bitmap_array, uint64_t array_length, uint64_t bitmap_base, uint64_t bitmap_pages)
{
	// first set all pages to used
	uint64_t i;
	for(i = 0; i < array_length; i++)
	{
		bitmap_array[i] = 0xffffffffffffffffULL;
	}

	// get pointers to each
	bitmap_4kb = (uint8_t*)bitmap_array;
	bitmap_4kb_length = (array_length * 8) / 2;	// halved because only need half for the 4kb, rest is for buddy system
	bitmap_8kb = (uint8_t*)(bitmap_4kb + bitmap_4kb_length);
	bitmap_8kb_length = (array_length * 8) / 4;
	bitmap_16kb = (uint8_t*)(bitmap_8kb + bitmap_8kb_length);
	bitmap_16kb_length = (array_length * 8) / 8;
	bitmap_32kb = (uint8_t*)(bitmap_16kb + bitmap_16kb_length);
	bitmap_32kb_length = (array_length * 8) / 16;

	// get pointer to memory map and entry count
	entries = (struct bios_memory_entry*)(KOFFSET + 0xf000);
	entry_count = *((uint16_t*)(KOFFSET + 0xfffe));

	// set 4kb pages according to free entries
	printf("building 4kb allocation bitmap");
	for(i = 0; i < entry_count; i++)
	{
		// check if entry is free
		if(entries[i].type == 1)
		{
			// entry is free
			// for each of the pages within the entry
			uint64_t k;
			for(k = 0; k < entries[i].pages; k++)
			{
				// get base address of page
				uint64_t page_base = entries[i].base + (k * 4096);

				// check if base is within bounds (in case something went wrong earlier)
				if((page_base < entries[i].limit) && (page_base >= 0x1000000))
				{
					// get page number
					uint64_t page_number = page_base / 4096;
					uint64_t byte = page_number / 8;
					uint64_t bit = page_number % 8;

					// set the page to free
					uint8_t b = 1 << bit;
					b = ~b;
					
					if(byte < bitmap_4kb_length)
					{
						bitmap_4kb[byte] &= b;
					}
				}
			}
		}
	}

	// set 4kb pages according to used entries (in case of overlap)
	for(i = 0; i < entry_count; i++)
	{
		// check if entry is not free
		if(entries[i].type != 1)
		{
			// entry is not free
			// for each of the pages within the entry
			uint64_t k;
			for(k = 0; k < entries[i].pages; k++)
			{
				// get base address of page
				uint64_t page_base = entries[i].base + (k * 4096);

				// check if base is within bounds (in case something went wrong earlier)
				if((page_base < entries[i].limit) && (page_base >= 0x1000000))
				{
					// get page number
					uint64_t page_number = page_base / 4096;
					uint64_t byte = page_number / 8;
					uint64_t bit = page_number % 8;

					// set the page to used
					uint8_t b = 1 << bit;
					
					if(byte < bitmap_4kb_length)
					{
						bitmap_4kb[byte] |= b;
					}
				}
			}
		}
	}
	
	// set pages used for the bitmap
	for(i = 0; i < bitmap_pages; i++)
	{
		// get base address of page
		uint64_t page_base = bitmap_base;
		page_base += (i * 4096);

		// get page number
		uint64_t page_number = page_base / 4096;
		uint64_t byte = page_number / 8;
		uint64_t bit = page_number % 8;

		// set the page to used
		uint8_t b = 1 << bit;
		bitmap_4kb[byte] |= b;
		
	}

	// set 8kb pages
	// for each bit in the 8kb bitmap
	printf("building 8kb allocation bitmap");
	for(i = 0; i < bitmap_8kb_length * 8; i++)
	{
		// get byte and bit in byte
		uint64_t byte = i / 8;
		uint64_t bit = i % 8;

		// get 4kb byte and bit
		uint64_t byte_4kb = (i * 2) / 8;
		uint64_t bit_4kb = (i * 2) % 8;

		// get state of 4kb pages
		uint8_t v = bitmap_4kb[byte_4kb] >> bit_4kb;
		v &= 0x3;

		// check the state
		if(v == 0)
		{
			// both 4kb pages are free
			// mark the 8kb page as free
			uint8_t b = 1 << bit;
			b = ~b;
			bitmap_8kb[byte] &= b;
		}
	}

	// set 16kb pages
	// for each bit in the 16kb bitmap
	printf("building 16kb allocation bitmap");
	for(i = 0; i < bitmap_16kb_length * 8; i++)
	{
		// get byte and bit in byte
		uint64_t byte = i / 8;
		uint64_t bit = i % 8;

		// get 8kb byte and bit
		uint64_t byte_8kb = (i * 2) / 8;
		uint64_t bit_8kb = (i * 2) % 8;

		// get state of 8kb pages
		uint8_t v = bitmap_8kb[byte_8kb] >> bit_8kb;
		v &= 0x3;

		// check the state
		if(v == 0)
		{
			// both 8kb pages are free
			// mark the 16kb page as free
			uint8_t b = 1 << bit;
			b = ~b;
			bitmap_16kb[byte] &= b;
		}
	}

	// set 32kb pages
	// for each bit in the 16kb bitmap
	printf("building 32kb allocation bitmap");
	for(i = 0; i < bitmap_32kb_length * 8; i++)
	{
		// get byte and bit in byte
		uint64_t byte = i / 8;
		uint64_t bit = i % 8;

		// get 16kb byte and bit
		uint64_t byte_16kb = (i * 2) / 8;
		uint64_t bit_16kb = (i * 2) % 8;

		// get state of 16kb pages
		uint8_t v = bitmap_16kb[byte_16kb] >> bit_16kb;
		v &= 0x3;

		// check the state
		if(v == 0)
		{
			// both 16kb pages are free
			// mark the 32kb page as free
			uint8_t b = 1 << bit;
			b = ~b;
			bitmap_32kb[byte] &= b;
		}
	}


	// return the number of available 4kb pages
	uint64_t free_pages = 0;
	uint64_t free_pages_sub_4gb = 0;
	uint64_t free_pages_post_4gb = 0;
	for(i = 0; i < bitmap_4kb_length; i++)
	{
		int k;
		for(k = 0; k < 8; k++)
		{
			uint8_t v = bitmap_4kb[i];
			v >>= k;
			v &= 1;
			if(!v)
			{
				free_pages++;

				if(((i * 8) + k) * 4096 >= 0x100000000ULL)
				{
					free_pages_post_4gb++;
				}
				else
				{
					free_pages_sub_4gb++;
				}
			}
		}
	}


	uint64_t pages_free_8k = 0;
	uint64_t pages_free_16k = 0;
	uint64_t pages_free_32k = 0;
	for(i = 0; i < bitmap_8kb_length; i++)
	{
		int k;
		for(k = 0; k < 8; k++)
		{
			uint8_t v = bitmap_8kb[i];
			v >>= k;
			v &= 1;
			if(!v)
			{
				pages_free_8k++;
			}
		}
	}
	for(i = 0; i < bitmap_16kb_length; i++)
	{
		int k;
		for(k = 0; k < 8; k++)
		{
			uint8_t v = bitmap_16kb[i];
			v >>= k;
			v &= 1;
			if(!v)
			{
				pages_free_16k++;
			}
		}
	}
	for(i = 0; i < bitmap_32kb_length; i++)
	{
		int k;
		for(k = 0; k < 8; k++)
		{
			uint8_t v = bitmap_32kb[i];
			v >>= k;
			v &= 1;
			if(!v)
			{
				pages_free_32k++;
			}
		}
	}
	
	printf("free 4kb pages %u = %uB (%uKB)", free_pages, free_pages * 4096, free_pages * 4);
	printf("free 8kb pages %u = %uB (%uKB)", pages_free_8k, pages_free_8k * 4096 * 2, pages_free_8k * 8);
	printf("free 16kb pages %u = %uB (%uKB)", pages_free_16k, pages_free_16k * 4096 * 4, pages_free_16k * 16);
	printf("free 32kb pages %u = %uB (%uKB)", pages_free_32k, pages_free_32k * 4096 * 8, pages_free_32k * 32);

	// setup physical allocation control variables
	phys_allocation_control = (struct physical_allocation_control*)(KOFFSET + PHYSICAL_PHYSICAL_ALLOC_CONTROL);

	// zero some values
	phys_allocation_control->sub_4gb_allocate_4kb_next = 0;
	phys_allocation_control->sub_4gb_allocate_8kb_next = 0;
	phys_allocation_control->sub_4gb_allocate_16kb_next = 0;
	phys_allocation_control->sub_4gb_allocate_32kb_next = 0;
	phys_allocation_control->post_4gb_allocate_4kb_next = 0;
	phys_allocation_control->post_4gb_allocate_8kb_next = 0;
	phys_allocation_control->post_4gb_allocate_16kb_next = 0;
	phys_allocation_control->post_4gb_allocate_32kb_next = 0;

	// set pre and post next page to allocate values
	for(i = 0; i < bitmap_4kb_length; i++)
	{
		int k;
		for(k = 0; k < 8; k++)
		{
			uint8_t v = bitmap_4kb[i];
			v >>= k;
			v &= 1;
			if(v == 0)
			{
				if(((i * 8) + k) * 4096 < 0x100000000)
				{
					if(phys_allocation_control->sub_4gb_allocate_4kb_next == 0)
						phys_allocation_control->sub_4gb_allocate_4kb_next = ((i * 8) + k) * 4096;
				}
				else
				{
					if(phys_allocation_control->post_4gb_allocate_4kb_next == 0)
						phys_allocation_control->post_4gb_allocate_4kb_next = ((i * 8) + k) * 4096;
				}
			}
		}
	}
	for(i = 0; i < bitmap_8kb_length; i++)
	{
		int k;
		for(k = 0; k < 8; k++)
		{
			uint8_t v = bitmap_8kb[i];
			v >>= k;
			v &= 1;
			if(v == 0)
			{
				if(((i * 8) + k) * 4096 * 2 < 0x100000000)
				{
					if(phys_allocation_control->sub_4gb_allocate_8kb_next == 0)
						phys_allocation_control->sub_4gb_allocate_8kb_next = ((i * 8) + k) * 4096 * 2;
				}
				else
				{
					if(phys_allocation_control->post_4gb_allocate_8kb_next == 0)
						phys_allocation_control->post_4gb_allocate_8kb_next = ((i * 8) + k) * 4096 * 2;
				}
			}
		}
	}
	for(i = 0; i < bitmap_16kb_length; i++)
	{
		int k;
		for(k = 0; k < 8; k++)
		{
			uint8_t v = bitmap_16kb[i];
			v >>= k;
			v &= 1;
			if(v == 0)
			{
				if(((i * 8) + k) * 4096 * 4 < 0x100000000)
				{
					if(phys_allocation_control->sub_4gb_allocate_16kb_next == 0)
						phys_allocation_control->sub_4gb_allocate_16kb_next = ((i * 8) + k) * 4096 * 4;
				}
				else
				{
					if(phys_allocation_control->post_4gb_allocate_16kb_next == 0)
						phys_allocation_control->post_4gb_allocate_16kb_next = ((i * 8) + k) * 4096 * 4;
				}
			}
		}
	}
	for(i = 0; i < bitmap_32kb_length; i++)
	{
		int k;
		for(k = 0; k < 8; k++)
		{
			uint8_t v = bitmap_32kb[i];
			v >>= k;
			v &= 1;
			if(v == 0)
			{
				if(((i * 8) + k) * 4096 * 8 < 0x100000000)
				{
					if(phys_allocation_control->sub_4gb_allocate_32kb_next == 0)
						phys_allocation_control->sub_4gb_allocate_32kb_next = ((i * 8) + k) * 4096 * 8;
				}
				else
				{
					if(phys_allocation_control->post_4gb_allocate_32kb_next == 0)
						phys_allocation_control->post_4gb_allocate_32kb_next = ((i * 8) + k) * 4096 * 8;
				}
			}
		}
	}


	// set pre and post memory available
	phys_allocation_control->post_4gb_memory_available = free_pages_post_4gb * 4096;
	phys_allocation_control->sub_4gb_memory_available = free_pages_sub_4gb * 4096;

	// set total amount of usable memory in system
	phys_allocation_control->total_memory = (16 * 1024 * 1024ULL) + (bitmap_pages * 4096) + (free_pages * 4096);

	// set amount used by the kernel
	phys_allocation_control->kernel_memory_allocated = (16 * 1024 * 1024) + (bitmap_pages * 4096);

	// set amount used by applications
	phys_allocation_control->application_memory_allocated = 0;

	// set amount available for use
	phys_allocation_control->total_memory_available = free_pages * 4096;

	// report memory amounts
	printf("sub  4gb 4kb next page 0x%x", phys_allocation_control->sub_4gb_allocate_4kb_next);
	printf("post 4gb 4kb next page 0x%x", phys_allocation_control->post_4gb_allocate_4kb_next);
	printf("sub  4gb 8kb next page 0x%x", phys_allocation_control->sub_4gb_allocate_8kb_next);
	printf("post 4gb 8kb next page 0x%x", phys_allocation_control->post_4gb_allocate_8kb_next);
	printf("sub  4gb 16kb next page 0x%x", phys_allocation_control->sub_4gb_allocate_16kb_next);
	printf("post 4gb 16kb next page 0x%x", phys_allocation_control->post_4gb_allocate_16kb_next);
	printf("sub  4gb 32kb next page 0x%x", phys_allocation_control->sub_4gb_allocate_32kb_next);
	printf("post 4gb 32kb next page 0x%x", phys_allocation_control->post_4gb_allocate_32kb_next);

	printf("sub  4gb memory available 0x%x %uKB %uMB", phys_allocation_control->sub_4gb_memory_available, phys_allocation_control->sub_4gb_memory_available / 1024, phys_allocation_control->sub_4gb_memory_available / 0x100000);
	printf("post 4gb memory available 0x%x %uKB %uMB", phys_allocation_control->post_4gb_memory_available, phys_allocation_control->post_4gb_memory_available / 1024, phys_allocation_control->post_4gb_memory_available / 0x100000); 
	printf("total usable memory in system 0x%x %uKB %uMB", phys_allocation_control->total_memory, phys_allocation_control->total_memory / 1024, phys_allocation_control->total_memory / 0x100000);
	printf("kernel memory allocated 0x%x %uKB %uMB", phys_allocation_control->kernel_memory_allocated, phys_allocation_control->kernel_memory_allocated / 1024, phys_allocation_control->kernel_memory_allocated / 0x100000);
	printf("application memory allocated 0x%x %uKB %uMB", phys_allocation_control->application_memory_allocated, phys_allocation_control->application_memory_allocated / 1024, phys_allocation_control->application_memory_allocated / 0x100000);
	printf("total memory available 0x%x %uKB %uMB", phys_allocation_control->total_memory_available, phys_allocation_control->total_memory_available / 1024, phys_allocation_control->total_memory_available / 0x100000);

	return free_pages;
}

static uint64_t get_low_bitmap_location(uint64_t pages_required)
{
	// get pointer to memory map and entry count
	entries = (struct bios_memory_entry*)(KOFFSET + 0xf000);
	entry_count = *((uint16_t*)(KOFFSET + 0xfffe));

	// go through each entry
	int i;
	for(i = 0; i < entry_count; i++)
	{
		// check if entry is available
		if(entries[i].type == 1)
		{
			// check if limit is below 4GB and section is at least partially above 16MB
			if((entries[i].limit < 0x100000000) && (entries[i].limit >= 0x1000000))
			{
				// check if this section has enough free pages in it
				if((entries[i].pages >= pages_required) && (entries[i].limit + 1 - (pages_required * 4096) >= 0x1000000))
				{
					// use this section
					if(entries[i].base < 0x1000000)
					{
						return 0x1000000;
					}
					else
					{
						// check the base is 2MB-aligned
						if(((entries[i].base / 0x200000) * 0x200000) == entries[i].base)
						{
							// base is 2MB-aligned, can use it
							return entries[i].base;
						}
						else
						{
							// base is not 2MB-aligned
							// create a 2MB-aligned base directly above the original
							uint64_t new_aligned_base = ((entries[i].base / 0x200000) * 0x200000) + 0x200000;

							// check if there is enough free 4kb pages after this new aligned base
							if(new_aligned_base + (pages_required * 4096) - 1 <= entries[i].limit)
							{
								return new_aligned_base;
							}
						}
					}
				}
			}
		}
	}

	return 0;
}

static uint64_t get_high_bitmap_location(uint64_t pages_required)
{
	// get pointer to memory map and entry count
	entries = (struct bios_memory_entry*)(KOFFSET + 0xf000);
	entry_count = *((uint16_t*)(KOFFSET + 0xfffe));

	// go through each entry
	int i;
	for(i = 0; i < entry_count; i++)
	{
		// check if entry is available
		if(entries[i].type == 1)
		{
			// check if limit is above 4GB
			if(entries[i].limit >= 0x100000000)
			{
				// check if this section has enough free pages in it
				if(entries[i].pages >= pages_required)
				{
					// use this section
					// check the base is 2MB-aligned
					if(((entries[i].base / 0x200000) * 0x200000) == entries[i].base)
					{
						// base is 2MB-aligned, can use it
						return entries[i].base;
					}
					else
					{
						// base is not 2MB-aligned
						// create a 2MB-aligned base directly above the original
						uint64_t new_aligned_base = ((entries[i].base / 0x200000) * 0x200000) + 0x200000;

						// check if there is enough free 4kb pages after this new aligned base
						if(new_aligned_base + (pages_required * 4096) - 1 <= entries[i].limit)
						{
							return new_aligned_base;
						}
					}
				}
			}
		}
	}

	return 0;
}

static uint64_t sort_memory_map()
{
	// get pointer to memory map and entry count
	entries = (struct bios_memory_entry*)(KOFFSET + 0xf000);
	entry_count = *((uint16_t*)(KOFFSET + 0xfffe));

	// change lengths to limits
	int i;
	for(i = 0; i < entry_count; i++)
	{
		// get new section end
		uint64_t end = entries[i].base;
		end = end + entries[i].length;
		entries[i].limit = end;

		// adjust type values
		entries[i].type = entries[i].type & 0xff;
	}

	// print them
	printf("Base               | Limit              | Type");
	for(i = 0; i < entry_count; i++)
	{
		printf("0x%a | 0x%a | %u", entries[i].base, entries[i].limit, entries[i].type);
	}

	// adjust boundaries so that they lie on 4kb aligned addresses
	for(i = 0; i < entry_count; i++)
	{
		// check type
		if(entries[i].type == 1) // free entry
		{
			// move base up to next 4kb-aligned address
			uint64_t base = entries[i].base;
			uint64_t remainder = base % 4096;
			base = base / 4096;
			base = base * 4096;
			if(remainder > 0)
				base += 4096;
			entries[i].base = base;

			// move limit down to 4kb-aligned address
			uint64_t limit = entries[i].length;
			limit = limit / 4096;
			limit = limit * 4096;
			entries[i].length = limit - 1;
		}
		else // used entry
		{
			// move base down to 4kb-aligned address
			uint64_t base = entries[i].base;
			base = base / 4096;
			base = base * 4096;
			entries[i].base = base;

			// move limit up to next 4kb-aligned address
			uint64_t limit = entries[i].length;
			uint64_t remainder = limit % 4096;
			limit = limit / 4096;
			limit = limit * 4096;
			if(remainder > 0)
				limit += 4096;
			entries[i].length = limit - 1;
			
		}
	}

	// count how many 4kb pages there are in each 4kb-aligned section
	for(i = 0; i < entry_count; i++)
	{
		// count for each entry
		uint64_t j = 0;
		uint64_t a = entries[i].base;
		while(a < entries[i].limit)
		{
			j++;
			a += 4096;
		}
		entries[i].pages = j;
	}

	// print new memory map
	printf("updated memory map:");
	printf("Base               | Limit              | Type | Pages");
	for(i = 0; i < entry_count; i++)
	{
		printf("0x%a | 0x%a | %u    | %u", entries[i].base, entries[i].limit, entries[i].type, entries[i].pages);
	}

	// get the highest memory address
	uint64_t highest_address = 0;
	for(i = 0; i < entry_count; i++)
	{
		if((entries[i].length > highest_address) && (entries[i].type == 1))
		{
			highest_address = entries[i].limit;
		}
	}

	// finished

#ifdef DEBUG_TEST_HIGH_ADDRESS
	return DEBUG_TEST_ADDRESS;
#else
	return highest_address;
#endif
}



//////////////////////////////////////////////////////////////////////////////////////////////////////
// main memory setup routine

uint64_t memory_init(uint32_t *error)
{
	// sort the bios provided memory map entries
	uint64_t highest_address = sort_memory_map();
	printf("highest address: 0x%a", highest_address);

	// get the required size of the bitmap
	uint64_t bitmap_size = ((highest_address + 1) / 4096) / 8;
	if(((highest_address + 1) / 4096) % 8 > 0)
		bitmap_size += 1;
	bitmap_size *= 2;

	// count how many 4kb pages are required
	uint64_t bitmap_pages = bitmap_size / 4096;
	if(bitmap_size % 4096 > 0)
		bitmap_pages += 1;

	// print info
	printf("reqiured bitmap size: %uB (%uKB) - %u page(s)", bitmap_size, bitmap_size / 1024, bitmap_pages);

	// determine where to get the memory from
	// if highest address is > 4GB + bitmap_size put the bitmap at 4GB
	uint64_t bitmap_address = 0;
	if((highest_address > 0x100000000) && ((0x100000000 + bitmap_size) < highest_address))
	{
		// put the bitmap at the start of a free memory gap above 4GB (2MB aligned)
		// find this gap
		bitmap_address = get_high_bitmap_location(bitmap_pages);

		// if no gap is suitable above 4GB, find one below 4GB
		if(bitmap_address == 0)
		{
			printf("WARNING: could not find bitmap location above 4GB");
			bitmap_address = get_low_bitmap_location(bitmap_pages);
			if(bitmap_address == 0)
			{
				printf("ERROR: could not find suitable location for memory bitmap below 4GB");
				*error = 2;
				return 0;
			}
		}
	}
	else
	{
		// put the bitmap at the start of a free memory gap below 4GB and above 16MB (2MB aligned)
		bitmap_address = get_low_bitmap_location(bitmap_pages);

		// check the returned address
		if(bitmap_address == 0)
		{
			// could not find a suitable address for the bitmap
			printf("ERROR: could not find suitable location for memory bitmap below 4GB");
			*error = 3;
			return 0;
		}
	}

	// have suitable 2MB-aligned bitmap address
	// print where bitmap will be based
	printf("placing bitmap at 0x%a - 0x%a", bitmap_address, bitmap_address + (bitmap_pages * 4096));

	// map the bitmap in the kernel address space
	uint64_t *bitmap_array = build_bitmap_virtual_space(bitmap_address, bitmap_pages);

	// build the bitmap
	build_bitmap(bitmap_array, bitmap_size / 8, bitmap_address, bitmap_pages);

	// set highest address
	phys_allocation_control->highest_address = highest_address;

	// initialise rest of memory system
	// finish initialising virtual memory controller
	build_virtual_bitmap(bitmap_pages);

	// return amount of usable memory
	*error = 0;
	return phys_allocation_control->total_memory_available;
}


//////////////////////////////////////////////////////////////////////////////////////////////////////
// second step for main memory setup (SMP aware stuff, mostly)

uint64_t memory_init_step2(uint32_t *error)
{
	// get amount of available memory
	uint64_t available_memory = phys_allocation_control->total_memory_available;

	// decide how big the lazy invalidation tables should be
	uint64_t table_size = 0;
	if(available_memory < (256 * 0x100000))	// 256MB
		table_size = 2048;
	else if(available_memory < (0x100000000ULL)) // 4GB
		table_size = 8192;
	else
		table_size = 32 * 1024;

	// allocate the global table
	KERNEL->lazy_invalidation_global = (struct lazy_invalidation_global_free_table*)kmalloc(sizeof(struct lazy_invalidation_global_free_table));
	printf("allocating %uB for global table header at 0x%a", sizeof(struct lazy_invalidation_global_free_table), KERNEL->lazy_invalidation_global);
	KERNEL->lazy_invalidation_global->entries = (struct lazy_invalidation_entry*)kmalloc(table_size);
	printf("allocating %uKB (%u entries) for the global table at 0x%a", table_size / 1024, table_size / 16, KERNEL->lazy_invalidation_global->entries);
	KERNEL->lazy_invalidation_global->lock.flags_state = 0;
	KERNEL->lazy_invalidation_global->lock.lock_key = 0;
	KERNEL->lazy_invalidation_global->max_entry_count = table_size / 16;
	KERNEL->lazy_invalidation_global->next_entry = 0;

	// allocate for each CPU
	KERNEL->lazy_invalidation_tables = (struct lazy_invalidation_table*)kmalloc(KERNEL->CPU_count * sizeof(struct lazy_invalidation_table));
	printf("allocating head tables for %u CPUs (%uB) at 0x%a", KERNEL->CPU_count, KERNEL->CPU_count * sizeof(struct lazy_invalidation_table), KERNEL->lazy_invalidation_tables);
	uint64_t i;
	for(i = 0; i < KERNEL->CPU_count; i++)
	{
		// allocate the new entry table
		KERNEL->lazy_invalidation_tables[i].new_entries = (struct lazy_invalidation_entry*)kmalloc(table_size);
		printf("allocating %uKB for CPU %u new table at 0x%a", table_size / 1024, i, KERNEL->lazy_invalidation_tables[i].new_entries);

		// allocate the free entry table
		KERNEL->lazy_invalidation_tables[i].free_entries = (struct lazy_invalidation_entry*)kmalloc(table_size);
		printf("allocating %uKB for CPU %u free table at 0x%a", table_size / 1024, i, KERNEL->lazy_invalidation_tables[i].free_entries);

		// initialise control variables
		KERNEL->lazy_invalidation_tables[i].lock.lock_key = 0;
		KERNEL->lazy_invalidation_tables[i].lock.flags_state = 0;
		KERNEL->lazy_invalidation_tables[i].next_entry_free = 0;
		KERNEL->lazy_invalidation_tables[i].next_entry_new = 0;
		KERNEL->lazy_invalidation_tables[i].max_entry_count = table_size / 16;
	}

	// finished
	return 1;
}